Năm 1964 trên cương vị Sư đoàn trưởng, ông dẫn Sư đoàn 325 vào miền Nam chiến đấu. Vào đến Tây Nguyên, do khó khăn về bảo đảm hậu cần và tình hình thay đổi, sư đoàn 325 phân tán; hai trung đoàn xuống khu 5, chỉ còn trung đoàn 101 ở lại mặt trận Tây Nguyên (mang mã hiệu chiến trường B3), ông làm Phó Tư lệnh B3. Ông đã trực tiếp chỉ đạo và chỉ huy trung đoàn 101 diệt gọn tiểu đoàn biệt động "Cọp Đen", rồi lại đánh thiệt hại nặng Trung đoàn 44 Quân lực Việt Nam Cộng hòa, tiêu diệt trung tá trung đoàn trưởng trung đoàn 44.

Năm 1965 Thượng tá Nguyễn Hữu An là tham mưu phó mặt trận B3 và tại đây, tháng 11 năm 1965, ông đã trực tiếp chỉ huy Trận Ia Đrăng, trận đánh nổi tiếng ở thung lũng Ia Đrăng đã tiêu diệt hoàn toàn 1 tiểu đoàn và làm thiệt hại nặng 1 tiểu đoàn kỵ binh Mỹ. Trận đánh phủ đầu và chiến thắng Sư đoàn Kỵ binh số 1 của Mỹ khi quân Mỹ vừa vào Việt Nam, một trận thắng mà chính các tướng lĩnh của Mỹ phải thừa nhận "Ia Đrăng - trận đánh đã làm thay đổi cuộc chiến tranh ở Việt Nam"[4]

Năm 1971, ông là Sư đoàn trưởng Sư đoàn 308 tham gia chiến đấu và góp phần cùng các đơn vị khác trong chiến thắng ở mặt trận đường 9-Nam Lào. Sau chiến thắng, ông lại được Quân ủy Trung ương điều sang giúp Mặt trận Pa thét Lào chiến đấu lấy lại Cánh đồng Chum. Đến cuối tháng 6 năm 1972, Quân ủy Trung ương lại điều ông chỉ huy sư đoàn 308 chiến đấu ở mặt trận Quảng Trị.